// 哈夫曼树是一种二叉树
// 哈夫曼树的特征是，会将权值越小的节点排在越下层
// 权值本身带有一定的逻辑意义，比如某个字符A出现的次数X，如果次数越多，那就越靠上层，次数越小就越靠下层

// https://www.bilibili.com/video/BV1kD4y1P76D/?spm_id_from=333.337.search-card.all.click&vd_source=4fd973d19cb5506a7c9f2d59e8ab5165

// https://www.bilibili.com/video/BV1f34y1t7Xj/?spm_id_from=333.337.search-card.all.click&vd_source=4fd973d19cb5506a7c9f2d59e8ab5165

const { findAllIndex, log, newID, isOdd } = require('../commonTool/zddtool.js');

class TreeNode {
    constructor(val, left = null, right = null) {
        this.id = newID();
        this.value = val;
        this.leftNode = left;
        this.rightNode = right;
    }

    getLeftDepth() {
        if (this.leftNode == null) {
            return 0;
        }

        return this.leftNode.getLeftDepth() + 1;
    }

    getRightDepth() {
        if (!this.rightNode) {
            return 0;
        }

        return this.getRightDepth(this.rightNode) + 1;
    }

    /**
     * 中序遍历
     */
    centerDesc() {
        let arrLeft = this.leftNode ? this.leftNode.centerDesc() : [];
        let arrRight = this.rightNode ? this.rightNode.centerDesc() : [];
        return arrLeft.concat([this.value]).concat(arrRight);
    }
}

class HuffmanTree {
    constructor(array) {
        this.orgTree = [];
        for (let ele of array) {
            this.orgTree.push(new TreeNode(ele));
        }

        this.tree = [];

        this.sortTree();
        this.init();
    }

    /**
     * 将数组按照元素值从小到大的数据排列
     */
    sortTree() {
        this.orgTree.sort((a, b) => {
            if (a.value != b.value) return a.value - b.value;
            return a.getLeftDepth() - b.getLeftDepth();
        });

        let arr = new Array(this.orgTree.length)
            .fill(-1)
            .map((_, i) => this.orgTree[i].value);

        log('new org tree');
        log(arr);
    }

    /**
     * 生成哈夫曼树
     */
    init() {
        // 具体哈夫曼树生成规则可以看上方置顶视频

        // 每次取出当前数组中最小的两个元素，为这两个元素生成父元素，并替换这俩元素到数组中继续循环
        while (this.orgTree.length > 1) {
            let ln = this.orgTree.shift();
            let rn = this.orgTree.shift();
            let nn = new TreeNode(ln.value + rn.value, ln, rn);

            if (ln.leftNode == null && ln.rightNode == null) this.tree.push(ln);
            if (rn.leftNode == null && rn.rightNode == null) this.tree.push(rn);
            this.tree.push(nn);

            log('new tree');
            log(
                new Array(this.tree.length)
                    .fill(-1)
                    .map((_, i) => this.tree[i].value)
            );

            this.orgTree = [nn].concat(this.orgTree);
            this.sortTree();
        }

        log('[huffmanTree init] complete');
        log(this.tree[this.tree.length - 1].centerDesc());
    }
}

module.exports = {
    TreeNode,
    HuffmanTree,
};

// let inputArray = [2, 3, 4];
// let inputArray = [2, 3, 4, 5, 6];
let inputArray = [5, 15, 40, 30, 10];
log('input is:');
log(inputArray);
new HuffmanTree(inputArray);
